package algorithm.leetcode;

import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @author wuwen
 * @since 2023/12/19
 */
public class NO169_多数元素 {
    public static void main(String[] args) {
        System.out.println(new SolutionPerformance().majorityElement(new int[]{2, 2, 1, 1, 1, 2, 3}));
    }

    static class SolutionPerformance {
        public int majorityElement(int[] handles) {
            int votes = 0, candidate = 0;
            for (int handle : handles) {
                if (votes == 0) {
                    candidate = handle;
                }
                votes += (candidate == handle ? 1 : -1);
            }
            // 如果不一定有的话则需要验证
            int validate = 0;
            for (int handle : handles) {
                if (handle == candidate) {
                    validate++;
                }
            }
            return validate > handles.length / 2 ? candidate : 0;
        }
    }

    static class SolutionSort {
        public int majorityElement(int[] handles) {
            Arrays.sort(handles);
            return handles[handles.length / 2];
        }
    }

    static class Solution {
        public int majorityElement(int[] handles) {
            int target = handles.length / 2;
            Map<Integer, Integer> counter = Arrays.stream(handles).boxed().collect(Collectors.toMap(k -> k, v -> 1, (ov, nv) -> ++ov));
            for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
                if (entry.getValue() > target) {
                    return entry.getKey();
                }
            }
            return 0;
        }
    }
}